package com.lwt.codetop.difference;

// 56. 合并区间

import java.util.ArrayList;
import java.util.List;

/**
 * 思路：差分：
 *          对于区间，我们进行加1操作，如果区间有交集那么两个区间的并集必然不为0，
 *          我们以0为分界点，将不同的区间进行拆分
 *      需要注意的是 [1,2] [3,4]本事没有交集，但是差分的话就是[1,4]合并了，为此我们要将区间进行扩展 X2倍
 */
public class MergeIntervals {
    private  static int N = (100000 + 10) * 2;
    public static void main(String[] args) {
        int[] b = new int[N];
        // 构建测试用例
        int[][] nums = {
                {1, 4},
                {4, 5},
        };
        // 1. 区间扩展 与差分操作
        for (int[] num : nums) {
            int l = num[0] * 2, r = num[1] * 2;
            insert(b, l, r, 1);
        }
        // 2. 求原数组
        for(int i = 1; i < N; i ++) b[i] += b[i - 1];
        // 3. 区间合并
        List<int[]> resList = new ArrayList<>();
        int start = -1;
        for (int i = 0; i < N; i++) {
            if(b[i] > 0 && start == -1){
                start = i; // 起点
            }
            else if(start != -1 && b[i] == 0){ // 找到一个区间的结尾
                resList.add(new int[]{start / 2, i / 2});
                start = -1; // 为下一次做准备
            }
        }
        int[][] res = resList.toArray(new int[][]{});
        for (int[] re : res) {
            System.out.println(re[0]+"---"+re[1]);
        }
    }
    private static void insert(int[] b, int l, int r, int c){
        b[l] += c;
        b[r + 1] -= c;
    }
}
